package com.leetcode;

import ds.ListNode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No206
 * @description
 * @date 2021/1/27 下午2:57
 */
public class No206 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(3);
        ListNode l3 = new ListNode(5);
        ListNode l4 = new ListNode(7);
        ListNode l5 = new ListNode(9);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode res = reverseList(l1);
        printListNode(res);

    }

    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(-1);
        while (head != null){
            ListNode nextNode = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = nextNode;
        }
        return dummy.next;
    }

    // 递归
    // https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void printListNode(ListNode l){
        if(l == null){
            System.out.println("empty listnode");
        }else{
            while (l != null){
                System.out.print(l.val);
                System.out.print( " ");
                l = l .next;
            }
        }
    }

}
